package com.concurrent.coline.part4.forkjoin.sort;

import com.concurrent.coline.part4.forkjoin.util.MakeArray;
import com.concurrent.coline.part4.forkjoin.util.MergeTool;

import java.util.Arrays;

/**
 * 来源：http://blog.csdn.net/yinwenjie
 */
public class NormalMergeSort {

    public static void main(String[] args) {
        int inits[] = MakeArray.makeArray();
        long beginTime = System.currentTimeMillis();
        int results[] = forkits(inits);
        long endTime = System.currentTimeMillis();
        // 如果参与排序的数据非常庞大，记得把这种打印方式去掉
        System.out.println("耗时=" + (endTime - beginTime));
    }

    // 拆分成较小的元素或者进行足够小的元素集合的排序
    private static int[] forkits(int source[]) {
        int sourceLen = source.length;
        if(sourceLen > 2) {
            int midIndex = sourceLen / 2;
            int result1[] = forkits(Arrays.copyOf(source, midIndex));
            int result2[] = forkits(Arrays.copyOfRange(source, midIndex , sourceLen));
            // 将两个有序的数组，合并成一个有序的数组
            int mer[] = MergeTool.joinInts(result1 , result2);
            return mer;
        }
        // 否则说明集合中只有一个或者两个元素，可以进行这两个元素的比较排序了
        else {
            // 如果条件成立，说明数组中只有一个元素，或者是数组中的元素都已经排列好位置了
            if(sourceLen == 1
                    || source[0] <= source[1]) {
                return source;
            } else {
                int targetp[] = new int[sourceLen];
                targetp[0] = source[1];
                targetp[1] = source[0];
                return targetp;
            }
        }
    }
}
